In this paper we continue the study of the edge intersection graphs of one(or zero) bend paths on a rectangular grid. That is, the edge intersectiongraphs where each vertex is represented by one of the following shapes:$\llcorner$,$\ulcorner$, $\urcorner$, $\lrcorner$, and we consider zero bendpaths (i.e., | and $-$) to be degenerate $\llcorner$s. These graphs, called$B_1$-EPG graphs, were first introduced by Golumbic et al (2009). We considerthe natural subclasses of $B_1$-EPG formed by the subsets of the four singlebend shapes (i.e., {$\llcorner$}, {$\llcorner$,$\ulcorner$},{$\llcorner$,$\urcorner$}, and {$\llcorner$,$\ulcorner$,$\urcorner$}) and wedenote the classes by [$\llcorner$], [$\llcorner$,$\ulcorner$],[$\llcorner$,$\urcorner$], and [$\llcorner$,$\ulcorner$,$\urcorner$]respectively. Note: all other subsets are isomorphic to these up to 90 degreerotation. We show that testing for membership in each of these classes isNP-complete and observe the expected strict inclusions and incomparability(i.e., [$\llcorner$] $\subsetneq$ [$\llcorner$,$\ulcorner$],[$\llcorner$,$\urcorner$] $\subsetneq$ [$\llcorner$,$\ulcorner$,$\urcorner$]$\subsetneq$ $B_1$-EPG; also, [$\llcorner$,$\ulcorner$] is incomparable with[$\llcorner$,$\urcorner$]). Additionally, we give characterizations andpolytime recognition algorithms for special subclasses of Split $\cap$[$\llcorner$].
展开▼
